package com.hr.leetcode.动态规划;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 周恒哲
 * @date 2020/05/29
 * 自底而上
 * 状态定义：dp[i][j]表示包含第i行第j列元素的最小路径和
 * 状态分析
 * 初始化：
 * dp最后一行=triangle最后一行
 * 常规：
 * triangle[i][j]一定会到达triangle[i+1][j]或者triangle[i+1][j+1],
 * 所以状态dp[i][j]一定等于dp[i+1][j]或者dp[i+1][j+1]的最小值+triangle[i][j]
 * 转换方程：dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
 **/
public class _120_三角形最小路径和 {
    public int minimumTotal(List<List<Integer>> triangle) {
        //判空（特判）
        if (triangle == null && triangle.size() == 0) {
            return 0;
        }
        // 加1可以不用初始化最后一行
        // 根据题意，行列值相同
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> rows = triangle.get(i);
            for (int j = 0; j < rows.size(); j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+rows.get(j);
            }
        }
        return dp[0][0];
    }
    //空间优化
    public int minimumTotal2(List<List<Integer>> triangle) {
        // 特判
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        // dp中记录了求第i行时，第i+1的最小路径和
        int[] dp = new int[triangle.size() + 1];

        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> rows = triangle.get(i);
            for (int j = 0; j < rows.size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + rows.get(j);
            }
        }
        return dp[0];
    }
}
